package com.zanbo.leetcode.largest_rectangle_in_histogram;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * 给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。  求在该柱状图中，能够勾勒出来的矩形的最大面积。
 *
 * @author zanbo
 * @program Solution
 * @since 2021-12-29 上午 10:18
 */
public class Largest_rectangle_in_histogram {
    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.largestRectangleArea(new int[]{2, 1, 5, 6, 2, 3}));
    }
}

class Solution {
    public int largestRectangleArea(int[] heights) {
        int[] tempints = new int[heights.length + 2];
        System.arraycopy(heights, 0, tempints, 1, heights.length);
        Deque<Integer> stack = new ArrayDeque<>();
        int area = 0;
        for (int i = 0; i < tempints.length; i++) {

            while (!stack.isEmpty() && tempints[i] < tempints[stack.peek()]) {
                int high = tempints[stack.pop()];
                area = Math.max(area, (i - stack.peek() - 1) * high);
            }
            stack.push(i);
        }
        return area;
    }
}